home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / oper_sys / emerald / emrldsys.lha / Language / Compiler / knowCT.c < prev    next >
C/C++ Source or Header  |  1990-08-16  |  19KB  |  677 lines
  1. /*
  2.  * @(#)knowCT.c    1.6  3/13/89
  3.  */
  4. #include "assert.h"
  5. #include "nodes.h"
  6. #include "map.h"
  7. #include "sequence.h"
  8. #include "trace.h"
  9. #include "semantics.h"
  10. #include "builtins.h"
  11. #include "primitives.h"
  12. #include "MyParser.h"
  13. #include "flags.h"
  14.  
  15. extern NodePtr getCTInfo();
  16.  
  17. Map nodeToStruct;
  18. extern Map manifestMap;
  19.  
  20. /*
  21.  * Handling of invoc nodes.  
  22.  * Stage 0:    ignore them
  23.  * Stage 1:    only depend on CT of target
  24.  * Stage 2:    depend on CT of target and args, and propogate CT information
  25.  *        the args to results of the operation.
  26.  */
  27.  
  28. #define STAGE1
  29.  
  30. static void CT_addDependent(parent, child)
  31. NodePtr parent, child;
  32. {
  33.   NodePtr childStruct;
  34.   NodePtr parentStruct;
  35.   parentStruct = (NodePtr) Map_Lookup(nodeToStruct, (int)parent);
  36.   if ((int)parentStruct == NIL) {
  37.     parentStruct = Construct(P_KNOWCT, 3, NN, NN, NN);
  38.     parentStruct->b.knowct.tag = parent->tag;
  39.     parentStruct->b.knowct.definingThing = parent;
  40.     Map_Insert(nodeToStruct, (int)parent, (int)parentStruct);
  41.   }
  42.   childStruct = (NodePtr) Map_Lookup(nodeToStruct, (int)child);
  43.   if ((int)childStruct == NIL) {
  44.     childStruct = Construct(P_KNOWCT, 3, NN, NN, NN);
  45.     childStruct->b.knowct.tag = child->tag;
  46.     childStruct->b.knowct.definingThing = child;
  47.     Map_Insert(nodeToStruct, (int)child, (int)childStruct);
  48.   }
  49.   Sequence_Add(&parentStruct->b.knowct.dependsOn, childStruct);
  50. }
  51.  
  52. extern void resolveGlobal();
  53.  
  54. static void CT_TryToAddDependent(parent, child)
  55. NodePtr parent, child;
  56. {
  57.   Symbol st;
  58.   switch (parent->tag) {
  59.     case P_SYMBOL:
  60.       st = (Symbol) parent;
  61.       if (st->isManifest) {
  62.     CT_addDependent(parent, Construct(T_NONE, 0));
  63.     return;
  64.       }
  65.       break;
  66.     case P_INVOC:
  67.       if (Map_Lookup(manifestMap, (int)parent) != NIL) {
  68.     CT_addDependent(parent, Construct(T_NONE, 0));
  69.     return;
  70.       }
  71.     default:
  72.       break;
  73.   }
  74.   switch (child->tag) {
  75.     case P_GLOBALREF:
  76.       resolveGlobal(child, (ValuePtr)NULL);
  77.       assert(child->b.globalref.value != NN);
  78.       CT_addDependent(parent, child->b.globalref.value);
  79.       break;
  80.     case T_NONE:
  81.     case P_INVOC:
  82.     case P_VECTORLIT:
  83.     case P_BOOLLIT:
  84.     case P_CHARLIT:
  85.     case P_INTLIT:
  86.     case P_REALLIT:
  87.     case P_STRINGLIT:
  88.     case P_BUILTINLIT:
  89.     case P_SELFLIT:
  90.     case P_ATLIT:
  91.     case P_OBLIT:
  92.     case P_NTHRESULT:
  93.     case P_EXP:
  94.     case P_UNARYEXP:
  95.       CT_addDependent(parent, child);
  96.       break;
  97.     case P_SYMREF:
  98.     case P_SYMDEF:
  99.       CT_addDependent(parent, (NodePtr) child->b.symref.symbol);
  100.       break;
  101.     case P_SYMBOL:
  102.       CT_addDependent(parent, child);
  103.       break;
  104.     default:
  105.       CT_addDependent(parent, Construct(T_NONE, 0));
  106.       break;
  107.   }
  108. }
  109.  
  110. /*ARGSUSED*/
  111. static void addResultSymbols(p, ob)
  112. NodePtr p, ob;
  113. {
  114. #ifdef JUNKKKK
  115.   NodePtr q, r;
  116.   assert(p->tag == P_OPDEF);
  117.   assert(ob->tag == P_OBLIT);
  118.   q = p->b.opdef.sig->b.opsig.results;
  119.   Sequence_For(r, q)
  120.     assert(r->tag == P_PARAM);
  121.     assert(r->b.param.sym->tag == P_SYMDEF);
  122.     CT_TryToAddDependent(ob, (NodePtr)r->b.param.sym->b.symdef.symbol);
  123.   Sequence_Next
  124. #endif
  125. }
  126.  
  127. extern NodePtr findObjectOperation(), OTLookup();
  128.  
  129. void buildKnowCTGraph(p)
  130. register NodePtr p;
  131. {
  132.   register NodePtr q, right, left, nth;
  133.  
  134.   if ((int)p <= 0x200) return;
  135.   switch (p->tag) {
  136.     case P_ASSIGNSTAT:
  137.       right = p->b.assignstat.right;
  138.       left = p->b.assignstat.left;
  139.       if (Sequence_Length(right) > 1) {
  140.     /* is a multiple assignment */
  141.     Sequence_For(q, left)
  142.       assert(q->tag == P_SYMREF);
  143.       CT_TryToAddDependent((NodePtr)q->b.symref.symbol,
  144.         right->b.children[z__z]);
  145.     Sequence_Next
  146.       } else if (Sequence_Length(left) == 1) {
  147.     q = left->b.children[0];
  148.     assert(q->tag == P_SYMREF);
  149.     CT_TryToAddDependent((NodePtr)q->b.symref.symbol, right->b.children[0]);
  150.       } else {
  151.     Sequence_For(q, left)
  152.       assert(q->tag == P_SYMREF);
  153.       nth = Construct(P_NTHRESULT, 0);
  154.       nth->b.nthresult.whichResult = z__z;
  155.       CT_TryToAddDependent(nth, right->b.children[0]);
  156.       CT_TryToAddDependent((NodePtr)q->b.symref.symbol, nth);
  157.     Sequence_Next
  158.       }
  159.       break;
  160.     case P_INVOC:
  161.       if ((q = (NodePtr)Map_Lookup(manifestMap, (int)p + 2)) != (NodePtr)NIL) {
  162.     return;
  163.       }
  164. #ifdef STAGE0
  165.       /* do not do anything */
  166. #else
  167. #ifdef STAGE1
  168.       CT_TryToAddDependent(p, p->b.invoc.target);
  169.       if (p->b.invoc.target->tag == P_SYMREF &&
  170.       p->b.invoc.target->b.symref.symbol->isManifest) {
  171.     NodePtr ct, opdef, results;
  172.     Symbol st;
  173.     ct = p->b.invoc.target->b.symref.symbol->value.CTinfo;
  174.     if (ct == NULL) {
  175.       TRACE2(knowct, 9, "CT of manifest symbol (0x%08x %s) is null", 
  176.         p->b.invoc.target->b.symref.symbol, 
  177.         ST_SymbolName(p->b.invoc.target->b.symref.symbol));
  178.     } else {
  179.       TRACE1(knowct, 9, "CT of invoc target is manifest (0x%08x)", ct);
  180.       opdef = findObjectOperation(ct, p->b.invoc.opname);
  181.       assert(opdef != NULL);
  182.       results = opdef->b.opdef.sig->b.opsig.results;
  183.       if (Sequence_Length(results) == 1) {
  184.         st = results->b.children[0]->b.param.sym->b.symdef.symbol;
  185.         TRACE2(knowct, 9, "The result symbol is \"%s\"(0x%08x)",
  186.           ST_SymbolName(st), st);
  187.         TRACE0(knowct, 9, "Adding result symbol as dependent of invoc");
  188.         CT_TryToAddDependent(p, (NodePtr)st);
  189.       }
  190.     }
  191.       }
  192. #else
  193. #ifdef STAGE2
  194.       Sequence_For(q, p->b.invoc.args)
  195.     assert(q->tag == P_ARG);
  196.     q = q->b.arg.exp;
  197.     CT_TryToAddDependent(p, q);
  198.       Sequence_Next
  199. #endif
  200. #endif
  201. #endif
  202.       break;
  203.     case P_CONSTDECL:
  204.       if (p->b.constdecl.sym->b.symdef.symbol->isManifest) {
  205.     CT_TryToAddDependent((NodePtr) p->b.constdecl.sym->b.symdef.symbol,
  206.       p->b.constdecl.sym->b.symdef.symbol->value.value);
  207.     break;
  208.       }
  209.     case P_VARDECL:
  210.       if (p->b.constdecl.value != NN)
  211.     CT_TryToAddDependent((NodePtr) p->b.constdecl.sym->b.symdef.symbol,
  212.       p->b.constdecl.value);
  213.       break;
  214.     case P_PARAM:
  215.       break;
  216.     case P_UNARYEXP:
  217.       break;
  218.     case P_EXP:
  219.       break;
  220.     case P_ATLIT:
  221.     case P_OBLIT:
  222.       CT_TryToAddDependent((NodePtr)p->b.oblit.name->b.symdef.symbol, p);
  223.       Sequence_For(q, p->b.oblit.setq)
  224.     assert(q->b.setq.inner->tag == P_SYMDEF);
  225.     CT_TryToAddDependent((NodePtr) q->b.setq.inner->b.symdef.symbol,
  226.       (NodePtr) q->b.setq.outer);
  227.       Sequence_Next
  228.       if (p->tag == P_OBLIT) {
  229.     Sequence_For(q, p->b.oblit.ops)
  230.       addResultSymbols(q, p);
  231.     Sequence_Next
  232.     if (p->b.oblit.monitor != NN) {
  233.       Sequence_For(q, p->b.oblit.monitor->b.monitor.ops)
  234.         addResultSymbols(q, p);
  235.       Sequence_Next
  236.     }
  237.       }
  238.       break;
  239.     case P_IMPORT:
  240.       break;
  241.     case P_EXPORT:
  242.       break;
  243.     case P_PRIMSTAT:
  244.       if (Sequence_Length(p->b.primstat.vars) <= 0) break;
  245.       if (p->b.primstat.number->tag == P_STRINGLIT) {
  246.     CT_TryToAddDependent((NodePtr)p->b.primstat.vars->b.children[0]->b.symref.symbol,
  247.       Construct(T_NONE, 0));
  248.       } else {
  249.     int pNum;
  250.     PrimitiveDescPtr pdp;
  251.     pNum = atoi(p->b.primstat.number->b.intlit.string);
  252.     for (pdp = primitives; pdp->number != 0 && pdp->number != pNum; pdp++) ;
  253.     assert(pdp->number != 0);
  254.     assert(pdp->isFunction);
  255.     if (pdp->atindex[0] == ANYINDEX) {
  256.       CT_TryToAddDependent((NodePtr)p->b.primstat.vars->b.children[0]->b.symref.symbol,
  257.         Construct(T_NONE, 0));
  258.     } else {
  259.       CT_TryToAddDependent((NodePtr)p->b.primstat.vars->b.children[0]->b.symref.symbol,
  260.         refToBuiltin(B_INSTCT, (int)pdp->atindex[0]));
  261.     }
  262.       }
  263.       break;
  264.     default:
  265.       break;
  266.   }
  267.   Sequence_For(q, p)
  268.     if ((int)q > 0x200) buildKnowCTGraph(q);
  269.   Sequence_Next
  270. }
  271.  
  272. void initializeKnowCT()
  273. {
  274.   nodeToStruct = Map_Create();
  275. }
  276.  
  277. static char *thingName(t)
  278. NodePtr t;
  279. {
  280.   static char buffer[128];
  281.   if (t->b.knowct.tag == P_SYMBOL) sprintf(buffer, "Symbol %s (0x%08x)",
  282.     ST_SymbolName((Symbol)(t->b.knowct.definingThing)), t->b.knowct.definingThing);
  283.   else sprintf(buffer, "%s (0x%08x) on line %d", tagNames[(int)t->b.knowct.tag],
  284.     t->b.knowct.definingThing, t->b.knowct.definingThing->lineNumber);
  285.   return(buffer);
  286. }
  287.  
  288. extern void findAll();
  289.  
  290. void displayKnowCTGraph()
  291. {
  292.   NodePtr thing, theStruct, q;
  293.   IFTRACE(knowct, 5) {
  294.     Map_For(nodeToStruct, thing, theStruct)
  295.       printf("struct 0x%08x %s", theStruct, thingName(theStruct));
  296.       if (theStruct->b.knowct.isDone) printf(" isDone");
  297.       if (theStruct->b.knowct.isOK) printf(" isOK");
  298.       printf(" depends on:\n");
  299.       Sequence_For(q, theStruct->b.knowct.dependsOn)
  300.     printf("\t\tstruct 0x%08x %s\n", q, thingName(q));
  301.       Sequence_Next
  302.     Map_Next
  303.   }
  304. }
  305.  
  306. Boolean isSameCT(a, b)
  307. NodePtr a, b;
  308. {
  309.   if (a->tag == P_ATLIT) {
  310.     assert(a->b.atlit.f.cannotBeConformedTo);
  311.     a = OTLookup(a->b.atlit.codeOID);
  312.   }
  313.   if (b->tag == P_ATLIT) {
  314.     assert(b->b.atlit.f.cannotBeConformedTo);
  315.     b = OTLookup(b->b.atlit.codeOID);
  316.   }
  317.   a = GETVALUE(a);
  318.   b = GETVALUE(b);
  319.   assert(a->tag == P_OBLIT && b->tag == P_OBLIT);
  320.   return(a->b.oblit.codeOID == b->b.oblit.codeOID);
  321. }
  322.  
  323. void propagateCTInfo(p)
  324. NodePtr p;
  325. {
  326.   NodePtr q, ct = NULL, oldCT, opdef, aSymbolStruct;
  327.   register Symbol st;
  328.   Boolean areAllSymbols = TRUE, foundFirstCT, foundDependent;
  329.  
  330.   if (p->tag == T_SEQUENCE) {
  331.     TRACE0(knowct, 3, "Trying to progagate to a set");
  332.     Sequence_For(q, p)
  333.       assert(q->tag == P_KNOWCT);
  334.       if (q->b.knowct.tag != P_SYMBOL) {
  335.     if (areAllSymbols) TRACE0(knowct, 3, "The set contains non-symbols");
  336.     TRACE1(knowct, 5, "%s", thingName(q));
  337.     areAllSymbols = FALSE;
  338.       }
  339.     Sequence_Next
  340.     if (areAllSymbols) {
  341.       TRACE0(knowct, 3, "The set contains only symbols, so trying harder");
  342.       foundFirstCT = FALSE;
  343.       foundDependent = FALSE;
  344.       Sequence_For(aSymbolStruct, p)
  345.     TRACE2(knowct, 4, "Looking at pre-reqs of 0x%08x %s", aSymbolStruct,
  346.       thingName(aSymbolStruct));    
  347.     Sequence_For(q, aSymbolStruct->b.knowct.dependsOn)
  348.       TRACE2(knowct, 5, "Looking at 0x%08x %s", q, thingName(q));
  349.       assert(q->tag == P_KNOWCT);
  350.       if (! q->b.knowct.isDone) continue; /* it is in this set */
  351.       foundDependent = TRUE;
  352.       if (!q->b.knowct.isOK) {
  353.         TRACE2(knowct, 5, "0x%08x %s not ok, give up", q, thingName(q));
  354.         ct = NULL;
  355.         break;
  356.       }
  357.       if (!foundFirstCT) {
  358.         ct = q->b.knowct.answer;
  359.         foundFirstCT = TRUE;
  360.       } else {
  361.         if (! isSameCT(ct, q->b.knowct.answer)) {
  362.           TRACE4(knowct, 5, "CT of 0x%08x %s (0x%08x) != 0x%08x, give up", q,
  363.         thingName(q), q->b.knowct.answer, ct);
  364.           ct = NULL;
  365.           break;
  366.         }
  367.       }
  368.     Sequence_Next
  369.       Sequence_Next
  370.       if (! foundDependent) {
  371.     TRACE1(knowct, 3, "Symbol %s has no dependents", thingName(p));
  372.     ct = NULL;
  373.       }
  374.     }
  375.     Sequence_For(aSymbolStruct, p)
  376.       if (ct != NULL) {
  377.     oldCT = ((Symbol)aSymbolStruct->b.knowct.definingThing)->value.CTinfo;
  378.     if (oldCT != NN) assert(isSameCT(oldCT, ct));
  379.     ((Symbol)aSymbolStruct->b.knowct.definingThing)->value.CTinfo = ct;
  380.       }
  381.       aSymbolStruct->b.knowct.isDone = TRUE;
  382.       aSymbolStruct->b.knowct.isOK = (ct != NULL);
  383.       aSymbolStruct->b.knowct.answer = ct;
  384.       TRACE4(knowct, 1, "Finalizing 0x%08x %s: %s 0x%08x", aSymbolStruct,
  385.     thingName(aSymbolStruct),
  386.     aSymbolStruct->b.knowct.isOK ? "know CT" : "do not know CT",
  387.     aSymbolStruct->b.knowct.answer);
  388.     Sequence_Next
  389.     return;
  390.   }
  391.   assert(p->tag == P_KNOWCT);
  392.   TRACE2(knowct, 3, "Propagating 0x%08x %s", p, thingName(p));
  393.   switch (p->b.knowct.tag) {
  394.     case T_NONE:
  395.       ct = NN;
  396.       break;
  397.     case P_INVOC:
  398. #ifdef STAGE0
  399.       /* do nothing */
  400.       ct = NULL;
  401. #else
  402. #ifdef STAGE1
  403.       p->b.knowct.answer = (NodePtr) Map_Lookup(manifestMap,
  404.     (int)p->b.knowct.definingThing + 1);
  405.       if ((int)p->b.knowct.answer != NIL) {
  406.     p->b.knowct.isDone = TRUE;
  407.     p->b.knowct.isOK = TRUE;
  408.     TRACE4(knowct, 1, "Finalizing (manifest) 0x%08x %s: %s 0x%08x", p, thingName(p),
  409.       p->b.knowct.isOK ? "know CT" : "know CT",
  410.       p->b.knowct.answer);
  411.     return;
  412.       }
  413.       q = p->b.knowct.dependsOn->b.children[0];
  414.       TRACE2(knowct, 4, "Looking at 0x%08x %s", q, thingName(q));
  415.       assert(q->tag == P_KNOWCT);
  416.       assert(q->b.knowct.isDone);
  417.       ct = NULL;
  418.       if (!q->b.knowct.isOK) {
  419.     TRACE2(knowct, 5, "0x%08x %s not ok, give up", q, thingName(q));
  420.       } else {
  421.     ct = q->b.knowct.answer;
  422.     TRACE3(knowct, 5, "0x%08x %s ok, ct = 0x%08x", q, thingName(q), ct);
  423.     opdef = findObjectOperation(ct, p->b.knowct.definingThing->b.invoc.opname);
  424.     assert(opdef != NULL);
  425.     q = opdef->b.opdef.sig->b.opsig.results;
  426.     if (Sequence_Length(q) == 1) {
  427.       st = q->b.children[0]->b.param.sym->b.symdef.symbol;
  428.       TRACE2(knowct, 5, "The result symbol is \"%s\"(0x%08x)",
  429.         ST_SymbolName(st), st);
  430.       ct = getCTInfo(st);
  431.     } else {
  432.       ct = NULL;
  433.     }
  434.       }
  435. #else
  436. #ifdef STAGE2
  437.       Sequence_For(q, p->b.knowct.dependsOn)
  438.     TRACE2(knowct, 4, "Looking at 0x%08x %s", q, thingName(q));
  439.     assert(q->tag == P_KNOWCT);
  440.     assert(q->b.knowct.isDone);
  441.     if (!q->b.knowct.isOK) {
  442.       TRACE2(knowct, 5, "0x%08x %s not ok, give up", q, thingName(q));
  443.       ct = NULL;
  444.       break;
  445.     }
  446.       Sequence_Next
  447.       ct = NULL;
  448. #endif
  449. #endif
  450. #endif
  451.       break;
  452.     case P_NTHRESULT:
  453. #ifdef STAGE0
  454.       /* do nothing */
  455.       ct = NULL;
  456. #else
  457. #ifdef STAGE1
  458.       assert(Sequence_Length(p->b.knowct.dependsOn) == 1);
  459.       q = p->b.knowct.dependsOn->b.children[0];
  460.       /* q now points to a P_INVOC struct */
  461.       assert(q->b.knowct.tag == P_INVOC);
  462.       assert(q->b.knowct.isDone);
  463.       assert(Sequence_Length(q->b.knowct.dependsOn) == 1);
  464.       q = p->b.knowct.dependsOn->b.children[0];
  465.       /* q now points to a the struct for the target */
  466.       TRACE2(knowct, 4, "Looking at 0x%08x %s", q, thingName(q));
  467.       assert(q->tag == P_KNOWCT);
  468.       assert(q->b.knowct.isDone);
  469.       ct = NULL;
  470.       if (!q->b.knowct.isOK) {
  471.     TRACE2(knowct, 5, "0x%08x %s not ok, give up", q, thingName(q));
  472.       } else {
  473.     ct = q->b.knowct.answer;
  474.     TRACE3(knowct, 5, "0x%08x %s ok, ct = 0x%08x", q, thingName(q), ct);
  475.     opdef = findObjectOperation(ct, p->b.knowct.definingThing->b.invoc.opname);
  476.     assert(opdef != NULL);
  477.     q = opdef->b.opdef.sig->b.opsig.results;
  478.     assert(Sequence_Length(q) > p->b.nthresult.whichResult);
  479.     st = q->b.children[p->b.nthresult.whichResult]->b.param.sym->b.symdef.symbol;
  480.     TRACE1(knowct, 5, "The result symbol is \"%s\"", ST_SymbolName(st));
  481.     ct = getCTInfo(st);
  482.       }
  483. #else
  484. #ifdef STAGE2
  485.       Sequence_For(q, p->b.knowct.dependsOn)
  486.     TRACE2(knowct, 4, "Looking at 0x%08x %s", q, thingName(q));
  487.     assert(q->tag == P_KNOWCT);
  488.     assert(q->b.knowct.isDone);
  489.     if (!q->b.knowct.isOK) {
  490.       TRACE2(knowct, 5, "0x%08x %s not ok, give up", q, thingName(q));
  491.       ct = NULL;
  492.       break;
  493.     }
  494.       Sequence_Next
  495.       ct = NULL;
  496. #endif
  497. #endif
  498. #endif
  499.       break;
  500.     case P_EXP:
  501.       switch (p->b.knowct.definingThing->b.exp.op) {
  502.     case KAND:
  503.     case KOR:
  504.     case OIDENTITY:
  505.     case ONOTIDENTITY:
  506.     case OCONFORMSTO:
  507.       ct = refToBuiltin(B_INSTCT, BOOLEANINDEX);
  508.       break;
  509.     default:
  510.       assert(FALSE);
  511.       break;
  512.       }
  513.       break;
  514.     case P_UNARYEXP:
  515.       switch (p->b.knowct.definingThing->b.unaryexp.op) {
  516.     case KISFIXED:
  517.     case KAWAITING:
  518.       ct = refToBuiltin(B_INSTCT, BOOLEANINDEX);
  519.       break;
  520.     case KLOCATE:
  521.       ct = refToBuiltin(B_INSTCT, NODEINDEX);
  522.       break;
  523.     default:
  524.       assert(FALSE);
  525.       break;
  526.       }
  527.       break;
  528.     case P_VECTORLIT:
  529.       ct = findInstCode(p->b.knowct.definingThing->b.vectorlit.vectorType);
  530.       break;
  531.     case P_BOOLLIT:
  532.       ct = refToBuiltin(B_INSTCT, BOOLEANINDEX);
  533.       break;
  534.     case P_CHARLIT:
  535.       ct = refToBuiltin(B_INSTCT, CHARACTERINDEX);
  536.       break;
  537.     case P_INTLIT:
  538.       ct = refToBuiltin(B_INSTCT, INTEGERINDEX);
  539.       break;
  540.     case P_REALLIT:
  541.       ct = refToBuiltin(B_INSTCT, REALINDEX);
  542.       break;
  543.     case P_STRINGLIT:
  544.       ct = refToBuiltin(B_INSTCT, STRINGINDEX);
  545.       break;
  546.     case P_BUILTINLIT:
  547.       ct = refToBuiltinFromToken(B_IT,
  548.     p->b.knowct.definingThing->b.builtinlit.whichType);
  549.       break;
  550.     case P_SELFLIT:
  551.       assert(FALSE);
  552.       break;
  553.     case P_ATLIT:
  554.       ct = refToBuiltin(B_INSTCT, SIGNATUREINDEX);
  555.       break;
  556.     case P_OBLIT:
  557.       ct = p->b.knowct.definingThing;
  558.       break;
  559.     case P_SYMBOL:
  560.       st = (Symbol) p->b.knowct.definingThing;
  561.       if (st->isManifest) {
  562.     p->b.knowct.isDone = TRUE;
  563.     p->b.knowct.isOK = TRUE;
  564.     p->b.knowct.answer = st->value.CTinfo;
  565.     TRACE4(knowct, 1, "Finalizing (manifest) 0x%08x %s: %s 0x%08x", p,
  566.       thingName(p),
  567.       p->b.knowct.isOK ? "know CT" : "know CT",
  568.       p->b.knowct.answer);
  569.     return;
  570.       }
  571.       foundFirstCT = FALSE;
  572.       Sequence_For(q, p->b.knowct.dependsOn)
  573.     TRACE2(knowct, 3, "Looking at 0x%08x %s", q, thingName(q));
  574.     assert(q->tag == P_KNOWCT);
  575.     assert(q->b.knowct.isDone);
  576.     if (!q->b.knowct.isOK) {
  577.       TRACE2(knowct, 5, "0x%08x %s not ok, give up", q, thingName(q));
  578.       ct = NULL;
  579.       break;
  580.     }
  581.     if (!foundFirstCT) {
  582.       ct = q->b.knowct.answer;
  583.       foundFirstCT = TRUE;
  584.     } else {
  585.       if (! isSameCT(ct, q->b.knowct.answer)) {
  586.         TRACE4(knowct, 4, "CT of 0x%08x %s (0x%08x) != 0x%08x, give up", q,
  587.           thingName(q), q->b.knowct.answer, ct);
  588.         ct = NULL;
  589.         break;
  590.       }
  591.     }
  592.       Sequence_Next
  593.       if (! foundFirstCT) {
  594.     TRACE1(knowct, 3, "Symbol %s has no dependents", thingName(p));
  595.     ct = NULL;
  596.       }
  597.       if (ct != NULL) {
  598.     oldCT = ((Symbol)p->b.knowct.definingThing)->value.CTinfo;
  599.     if (!bflag && oldCT != NN) assert(isSameCT(oldCT, ct));
  600.     ((Symbol)p->b.knowct.definingThing)->value.CTinfo = ct;
  601.       }
  602.       break;
  603.     default:
  604.       break;
  605.   }
  606.   p->b.knowct.isDone = TRUE;
  607.   p->b.knowct.isOK = (ct != NULL);
  608.   p->b.knowct.answer = ct;
  609.   TRACE4(knowct, 1, "Finalizing 0x%08x %s: %s 0x%08x", p, thingName(p),
  610.     p->b.knowct.isOK ? "know CT" : "do not know CT",
  611.     p->b.knowct.answer);
  612. }
  613.  
  614. static int count = 0;
  615. static NodePtr SCstack = NULL;
  616. static NodePtr SCComponent = NULL;
  617.  
  618. #define min(A, B) ((A) < (B) ? (A) : (B))
  619.  
  620. void SearchC(v)
  621. register NodePtr v;
  622. {
  623.   register NodePtr x, w;
  624.   v->b.knowct.marked = TRUE;
  625.   v->b.knowct.number = count++;
  626.   v->b.knowct.lowLink = v->b.knowct.number;
  627.   Sequence_Add(&SCstack, v);
  628.   v->b.knowct.onStack = TRUE;
  629.   Sequence_For(w, v->b.knowct.dependsOn)
  630.     if (! w->b.knowct.marked) {
  631.       SearchC(w);
  632.       v->b.knowct.lowLink = min(v->b.knowct.lowLink, w->b.knowct.lowLink);
  633.     } else {
  634.       if (w->b.knowct.number < v->b.knowct.number && w->b.knowct.onStack) {
  635.     v->b.knowct.lowLink = min(w->b.knowct.number, v->b.knowct.lowLink);
  636.       }
  637.     }
  638.   Sequence_Next
  639.   if (v->b.knowct.lowLink == v->b.knowct.number) {
  640.     TRACE0(knowct, 1, "------");
  641.     Sequence_ReverseFor(x, SCstack)
  642.       SCstack->nChildren --;
  643.       assert(x->b.knowct.onStack);
  644.       x->b.knowct.onStack = FALSE;
  645.       if (SCComponent == NULL && x == v) {
  646.     /* this is the only element of the component */
  647.     SCComponent = x;
  648.       } else {
  649.     Sequence_Add(&SCComponent, x);
  650.       }
  651.       TRACE2(knowct, 2, "struct 0x%08x %s", x, thingName(x));
  652.       if (x == v) break;
  653.     Sequence_Next
  654.     propagateCTInfo(SCComponent);
  655.     if (SCComponent->tag == T_SEQUENCE) {
  656.       free((char *)SCComponent);
  657.     }
  658.     SCComponent = NULL;
  659.   }
  660. }
  661.  
  662. void FindAll()
  663. {
  664.   NodePtr theThing, theStruct;
  665.   Map_For(nodeToStruct, theThing, theStruct)
  666.     if (! theStruct->b.knowct.marked) SearchC(theStruct);
  667.   Map_Next
  668. }
  669.  
  670. void doKnowCTs(p)
  671. NodePtr p;
  672. {
  673.   buildKnowCTGraph(p);
  674.   displayKnowCTGraph();
  675.   FindAll();
  676. }
  677.